Section: New Results

Code-based cryptography

Participants : Matthieu Finiasz, Grégory Landais, Rafael Misoczki, Ayoub Otmani, Nicolas Sendrier, Jean-Pierre Tillich.

Most popular public-key cryptographic schemes rely either on the factorization problem (RSA, Rabin), or on the discrete logarithm problem (Diffie-Hellman, El Gamal, DSA). These systems have evolved and today instead of the classical groups ($𝐙/n𝐙$) we may use groups on elliptic curves. They allow a shorter block and key size for the same level of security. An intensive effort of the research community has been and is still being conducted to investigate the main aspects of these systems: implementation, theoretical and practical security. It must be noted that these systems all rely on algorithmic number theory. As they are used in most, if not all, applications of public-key cryptography today (and it will probably remain so in the near future), cryptographic applications are thus vulnerable to a single breakthrough in algorithmics or in hardware (a quantum computer can break all those scheme).

Diversity is a way to dilute that risk, and it is the duty of the cryptographic research community to prepare and propose alternatives to the number theoretic based systems. The most serious tracks today are lattice-based cryptography (NTRU,...), multivariate cryptography (HFE,...) and code-based cryptography (McEliece encryption scheme,...). All these alternatives are referred to as post-quantum cryptosystems, since they rely on difficult algorithmic problems which would not be solved by the coming-up of the quantum computer.

The code-based primitives have been investigated in details within the project-team. The first cryptosystem based on error-correcting codes was a public-key encryption scheme proposed by McEliece in 1978; a dual variant was proposed in 1986 by Niederreiter. We proposed the first (and only) digital signature scheme in 2001. Those systems enjoy very interesting features (fast encryption/decryption, short signature, good security reduction) but also have their drawbacks (large public key, encryption overhead, expensive signature generation). Some of the main issues in this field are

• security analysis , implementation and practicality of existing solutions,

• reducing the key size, e.g., by using rank metric instead of Hamming metric, or by using particular families of codes,

• address new functionalities, like hashing or symmetric encryption.

Recent results:

• A distinguishing attack on high rate Goppa codes [25] . This results does not lead to an attack on any code based cryptosystem, but, in some particular cases, it invalidates the security reduction. It was conjectured that there was no such distinguishers.

• A new class of codes for McEliece type cryptosystems offering more versatility [22]

• A generic attack on one-time signature based on codes (KKS type) [27] .

• A improvement of generic decoding techniques when addressing multiple targets [28] .